package leetcode.lcp0008;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int[] getTriggerTime(int[][] increase, int[][] requirements) {
		int len = increase.length;
		int[][] days = new int[len + 1][3];
		for (int i = 1; i <= len; i++) {
			days[i][0] = days[i - 1][0] + increase[i - 1][0];
			days[i][1] = days[i - 1][1] + increase[i - 1][1];
			days[i][2] = days[i - 1][2] + increase[i - 1][2];
		}
		// 0,0,0,
		// 2,8,4,
		// 4,13,4,
		// 14,22,12,
		// [[2,11,3],[15,10,7],[9,17,12],[8,1,14]]
		int[] ans = new int[requirements.length];
		for (int i = 0; i < requirements.length; i++) {
			int[] req = requirements[i];
			int c = req[0], r = req[1], h = req[2];
			int d1 = this.search(days, 0, len, 0, c);
			int d2 = this.search(days, d1, len, 1, r);
			int d3 = this.search(days, d2, len, 2, h);
			ans[i] = d3;
		}
		return ans;

	}

	private int search(int[][] days, int l, int r, int index, int target) {
		if (l == -1) {
			return -1;
		}
		int ans = -1;
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			if (days[mid][index] >= target) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(H.str2array3("[0]"), this.getTriggerTime(H.str2array1("[[1,1,1]]"), H.str2array1("[[0,0,0]]")));
		H.compare(H.str2array3("[2,-1,3,-1]"), this.getTriggerTime(H.str2array1("[[2,8,4],[2,5,0],[10,9,8]]"),
				H.str2array1("[[2,11,3],[15,10,7],[9,17,12],[8,1,14]]")));
		H.compare(H.str2array3("[-1,4,3,3,3]"), this.getTriggerTime(H.str2array1("[[0,4,5],[4,8,8],[8,6,1],[10,10,0]]"),
				H.str2array1("[[12,11,16],[20,2,6],[9,2,6],[10,18,3],[8,14,9]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
